package com.major.sort.radixsorting;

public class RadixSort {

    public static void radixSort(int[] arr) {
        // 得到最大的数的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int len = (max + "").length();
        // 创建二位数组，每个一维数组表示桶
        int[][] bucket = new int[10][arr.length];
        // 创建桶内数据计数数组，用于将桶内元素放回数组，计数用
        int[] bucketEleCount = new int[10];

        for (int n = 1, k = 0; k <= len; k++, n *= 10) {
            // 依次将数据 放入桶中
            for (int value : arr) {
                // 得到个位值
                int ele = value / n % 10;
                bucket[ele][bucketEleCount[ele]] = value;
                bucketEleCount[ele]++;

            }
            // 将数据放回数组
            int index = 0;
            for (int i = 0; i < bucketEleCount.length; i++) {
                // 有数据才放回数组，
                if (bucketEleCount[i] != 0) {                // 表示第i桶有数据
                    for (int j = 0; j < bucketEleCount[i]; j++) {
                        //arr[index] = bucket[i][bucketEleCount[j]];
                        arr[index] = bucket[i][j];          // 第i桶第j个元素
                        index++;
                    }
                    bucketEleCount[i] = 0;
                }
            }
        }
    }
}
